package org.regotto.basics.graph;

import org.regotto.basics.dataStruct.GraphInfo;
import org.regotto.common.Utils;

import java.util.Scanner;

public class BellmanFord {

    static final int N = 1000, M = 1000;
    static int[] dis = new int[N], bak = new int[N];
    static int n, m, k;
    static GraphInfo[] e = new GraphInfo[N];

    public static int bf() {
        Utils.full(dis, 0x3f3f3f3f);
        dis[1] = 0;
        Utils.arrCopy(bak, dis, dis.length);
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < m; j++) {
                int a = e[i].a, b = e[i].b, c = e[i].c;
                dis[b] = Math.min(dis[b], bak[a] + c);
            }
        }
        return dis[n] > 0x3f3f3f3f / 2 ? -1 : dis[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 0; i < m; i++) {
            e[i] = new GraphInfo(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        int t = bf();
        System.out.println();
    }

}
